package arithmetic.LeetCode;

/**
 * https://leetcode.cn/problems/minimum-limit-of-balls-in-a-bag/
 *
 * @author jiangfeng on 2022/12/20
 */
public class LimitBall1760 {

    public static void main(String[] args) {
        // System.out.println(minimumSize(new int[] {9}, 2));
        System.out.println(minimumSize(new int[] {2,4,8,2}, 4)); // 输出1预期2
    }

    public  static int minimumSize(int[] nums, int maxOperations) {
        // 1. 找最大值
        // 2. 定义左边界是1, 右边界是最大值
        // 3.[定义]使用二分法找到一个数 m,使得数组内所有的都小于等于m
        //    3.1对左右边界二分, 尝试使用中间数m
        //    3.2判断方式:用数组每个元素除以m,所得的数n为对此元素操作n次即可满足上[定义],
        //    特殊情况: 如果刚刚好能整除则只需n-1次操作.
        //  例: 元素小于等于m,则不需操作即满足上[定义],元素[m+1,2m]时,操作一次可满足上[定义]
        int max = 0;
        for (int n : nums) {
            max = Math.max(max, n);
        }
        int l = 1, r = max, pos = 0;
        while (l <= r) {
            int m = l+((r-l) >> 1);
            int opt =0;
            for (int n : nums) {
                opt += n / m - (n % m == 0 ? 1 : 0);
            }
            if (opt <= maxOperations) {
                // 值定大了,还可以小点
                r = m - 1;
                pos = m;
            } else {
                // 大了
                l = m+1;
            }
        }
        return pos;
    }
}
